package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //地图分析
        class Solution {
            // 四联通方向：上、下、左、右
            int[] dx = {0, 0, -1, 1};
            int[] dy = {-1, 1, 0, 0};

            public int maxDistance(int[][] grid) {
                int m = grid.length, n = grid[0].length;
                boolean[][] vis = new boolean[m][n];
                Queue<int[]> q = new LinkedList<>();

                // 1) 多源起点：所有陆地入队
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == 1) {
                            q.offer(new int[]{i, j});
                            vis[i][j] = true;
                        }
                    }
                }

                // 2) 边界判定：无陆地或全为陆地
                if (q.isEmpty() || q.size() == m * n) return -1;

                // 3) 分层 BFS 扩散
                int ret = 1; // 层计数（从所有陆地出发的外层距离）
                while (!q.isEmpty()) {
                    int size = q.size();
                    while (size-- > 0) {
                        int[] cur = q.poll();
                        int a = cur[0], b = cur[1];

                        // 扩展四邻
                        for (int k = 0; k < 4; k++) {
                            int x = a + dx[k], y = b + dy[k];
                            // 界内且未访问：首次被触达的海洋
                            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                                q.offer(new int[]{x, y});
                                vis[x][y] = true;
                                // 可选：记录该海洋格到最近陆地的距离层数
                                grid[x][y] = ret;
                            }
                        }
                    }
                    ret++; // 本层处理完毕，进入下一层
                }

                // 4) 返回修正后的最大距离
                return ret - 2; // ret 最后多加 1，且初始为 1，合计减 2
            }
        }

        //课程表
        class Solution2 {
            public boolean canFinish(int n, int[][] p) {
                int[] in = new int[n];
                Map<Integer, List<Integer>> edges = new HashMap<>();

                // 建图：b -> a，并统计入度
                for (int[] e : p) {
                    int a = e[0], b = e[1];
                    edges.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
                    in[a]++;
                }

                // 入度为 0 的课程编号入队
                Queue<Integer> q = new LinkedList<>();
                for (int i = 0; i < n; i++) {
                    if (in[i] == 0) q.offer(i);
                }

                // Kahn 拓扑排序
                int visited = 0;
                while (!q.isEmpty()) {
                    int t = q.poll();
                    visited++;

                    for (int nxt : edges.getOrDefault(t, Collections.emptyList())) {
                        if (--in[nxt] == 0) q.offer(nxt);
                    }
                }

                // 全部弹出 => 无环 => 可以学完
                return visited == n;
            }
        }

    }
}